This invention relates generally to the field of the design of electronic devices, such as printed circuits boards and semiconductor devices, and more particularly to improvements in routing of a number of nets in tracks of a channel of an electronic devices.
Many automatic layout systems, especially VLSI circuits, apply channel routing as the basic interconnection function. However, many routers can only cope with the geometric regularity of standard cell and gate array designs. As a result these prior art automatic layout systems can not route channels with geometric generality, i.e. terminals that can have different width and irregular spacing, and simultaneously guaranteeing completion of all routes.
From Bryan Preas, xe2x80x9cChannel Routing With Non-Terminal Doglegsxe2x80x9d, Proc. The European Design Automation Conference, Glasgow, Scotland, 1990, pp 451-458, a method for resolving cyclic vertical constrains using a generalized channel model is known. When this method is combined with a constraint based channel router, routing completion can be guaranteed for a large class of channel geometries. This method is implemented with a constrain-based, alternating-edge dogleg channel router. The method resolves cyclic constrains by adding non-terminal doglegs to enough wire segments to break all of the constraint cycles. The altered wire segments and the resulting acyclic constraint graph can be used as input to most constraint-based channel routers.
The common disadvantage of all prior art channel routers is that they can not deal with multi-layer channels having overlapping terminals because vertical constrains can not be resolved. Also, if there are terminals on more than two sides of the channel the prior art routers do not work.
It is therefore an underlying problem of the invention to provide an improved method for routing a number of nets and tracks of a channel, a method for manufacturing an electronic device and an electronic device featuring improved routing.
The problem of the invention is solved basically by applying the feature laid down in the independent claims. Further preferred embodiments are set out in the dependent claims.
The invention is advantageous in that is allows to deal with channel geometries in which individual terminals can create incoming and outgoing edges in the corresponding vertical constraint graph at the same time. This allows to use the invention for routing of multi-layer channels having overlapping terminals on different layers and also with channels having terminals on every side. The invention is also applicable for other kinds of channels because of its generality.
According to a preferred embodiment of the invention a critical node of the vertical constraint graph of the channel to be routed is split in two or more new nodes in order to resolve vertical constrains. To find the optimum number of new nodes a graph coloring method is employed. This guarantees that only a minimum of new nodes results from the splitting operation and thus a minimum number of row segments to route the same net.
Another advantage of the method of the invention is that it is adopted to be carried out automatically by means of a computer program which requires data descriptive of the channel geometry and the nets to be routed as input data. This allows it to minimize design cycle times.
An electronic device that is routed and produced according to the principles of the invention features improved compactness of design due to the improved routing. The improved routing also results in a minimized overall wiring length as well as minimized requirements for precious silicon floor space in the case of a semiconductor device.
These advantages have a beneficial impact on signal propagation delays and power dissipation. As a consequence the overall operational speed of such an electronic device is improved. For the case of a clocked electronic device the clocking frequency can be increased as compared to prior art devices.